#ifndef GAMEENGINE_GEOMETRY_TOPOLOGY_HALFEDGE_HPP
#define GAMEENGINE_GEOMETRY_TOPOLOGY_HALFEDGE_HPP

#include <set>

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

//=================================================================================
// Implementation of the HalfEdge class

//! Default constructor
template <class T>
HalfEdge<T>::HalfEdge() : origin_(nil), face_(nil), next_edge_(nil), opposite_edge_(nil) {}

//! Explicit constructor
/*!
 @param origin The origin from which this half-edge is leaving
 @param face The face to which this half-edge is associated
 @param next_edge The next edge of the polygon
 @param opposite_edge The opposite edge, i.e., the edge of an adjacent polygon
 */
template <class T>
HalfEdge<T>::HalfEdge(Vertex* origin, Face* face, HalfEdge* next_edge, HalfEdge* opposite_edge) :
	origin_(origin), face_(face), next_edge_(next_edge), opposite_edge_(opposite_edge) {}

//! Copy constructor
/*!
 @param rhs The half-edge to copy
 */
template <class T>
HalfEdge<T>::HalfEdge(const HalfEdge& rhs) :
	origin_(rhs.origin_), face_(rhs.face_), next_edge_(rhs.next_edge_), opposite_edge_(rhs.opposite_edge_) {}

//! Destructor
template <class T>
HalfEdge<T>::~HalfEdge() {}

//! Assignment operator
/*!
 @param rhs The half-edge to copy
 */
template <class T>
HalfEdge<T>& HalfEdge<T>::operator=(const HalfEdge& rhs) {
	if ( &rhs != this ) {
		origin_ = rhs.origin_;
		face_ = rhs.face_;
		next_edge_ = rhs.next_edge_;
		opposite_edge_ = rhs.opposite_edge_;
	}
	return *this;
}

//! Test if edge is belongs to the virtual exterior face
/*!
 @return True if edge belongs to the virtual exterior face, false otherwise
 */
template <class T>
bool HalfEdge<T>::exterior_edge() const {
	return ( face_ == nil );
}

//! Accessor to the origin from which this half-edge is leaving
/*!
 @return A pointer to the origin from which this half-edge is leaving
 */
template <class T>
typename HalfEdge<T>::Vertex* HalfEdge<T>::origin() const {
	return origin_;
}

//! Accessor to the face associated to this half-edge
/*!
 @return A pointer to the face associated to this half-edge (may be nil if this edge
         belongs to the exterior virtual face)
 */
template <class T>
typename HalfEdge<T>::Face* HalfEdge<T>::face() const {
	return face_;
}

//! Accessor to the next half-edge of the face
/*!
 @return A pointer to the next half-edge of the face
 */
template <class T>
HalfEdge<T>* HalfEdge<T>::next_edge() const {
	return next_edge_;
}

//! Accessor to the opposite half-edge
/*!
 @return A pointer to the opposite half-edge
 */
template <class T>
HalfEdge<T>* HalfEdge<T>::opposite_edge() const {
	return opposite_edge_;
}

//! Iterate through the face until the previous half-edge is found
/*!
 *  This function is quite costly, since up to N iterations must be
 *  performed to find the previous half-edge (where N is the number of
 *  edges that belong to the edge face).
 *
 *  This function assumes that the face to which the half-edge belongs
 *  is valid. There are several possible results if the face is invalid:<br>
 *  1. If face is a virtual exterior face, a null pointer will
 *     be returned.<br>
 *  2. If face defines an open half-edge path, a null pointer will be returned.<br>
 *  3. If face defines an invalid edge loop, this function will result
 *     in an infinite loop. An example of a face producing such an infinite
 *     loop could be: (example is written in pseudo-code)
 *  @code
 *  this_edge->next = edge1
 *  edge1->next = edge2
 *  edge2->next = edge3
 *  edge3->next = edge1
 *  @endcode
 *     Hence, the face defines a loop between edge1, edge2 and edge3, but
 *     never loops back to this_edge. Detecting such issues would be too
 *     costly to be practical - client code is therefore responsible for
 *     the validity of the face prior to calling this function.
 *
 @return A pointer to the previous half-edge (may be nil if such a half-edge
         cannot be found in the face).
 */
template <class T>
HalfEdge<T>* HalfEdge<T>::get_previous_edge() const {
	// Get next edge and check it
	HalfEdge<T>* res = next_edge_;
	if ( res == this ) return res;
	if ( res == nil ) return nil;

	// Iterate through the edges until previous edge is found
	while ( res->next_edge_ != this ) {
		if ( res->next_edge_ == nil ) return nil;
		res = res->next_edge_;
	}

	// Return previous edge
	return res;
}

//! Change the origin from which this half-edge is leaving
/*!
 @param origin A pointer to the origin from which this half-edge should be leaving
 @return True if function succeeded, false otherwise. Origin may not be changed if
         client code provided a null pointer.
 */
template <class T>
bool HalfEdge<T>::set_origin(Vertex* origin) {
	if ( origin == nil ) return false;
	origin_ = origin;
	return true;
}

//! Change the face associated to this half-edge
/*!
 @param face A pointer to the face to which this half-edge should be associated. May
        be nil to indicate the virtual exterior face
 @return Always return true.
 */
template <class T>
bool HalfEdge<T>::set_face(Face* face) {
	face_ = face;
	return true;
}

//! Change the next half-edge of the face
/*!
 @param next_edge A pointer to the new next half-edge of the face. May be nil for
                  the virtual exterior face, since the virtual exterior face cannot
				  be iterated.
 @return Always return true.
 */
template <class T>
bool HalfEdge<T>::set_next_edge(HalfEdge<T>* next_edge) {
	next_edge_ = next_edge;
	return true;
}

//! Change the opposite half-edge of the face
/*!
 @param opposite_edge A pointer to the new opposite half-edge of the face
 @param notify_other_edge If set to true, the new opposite edge is also updated to point to this half-edge
 @return True if function succeeded, false otherwise. The opposite half-edge may not
         be changed if client code provided a null pointer.
 */
template <class T>
bool HalfEdge<T>::set_opposite_edge(HalfEdge<T>* opposite_edge, bool notify_other_edge) {
	if ( opposite_edge == nil ) return false;
	opposite_edge_ = opposite_edge;
	if ( notify_other_edge == true ) {
		return opposite_edge->set_opposite_edge(this, false);
	}
	return true;
}

//! Detect the type of the half-edge
/*!
 @return The type of the half-edge. This can either be Invalid for half-edges that are topologically
         incorrect, VirtualBorder for half-edges that belong to the virtual border edge, or Internal
		 for half-edges that are shared by two real faces.
 */
template <class T>
typename HalfEdge<T>::Type HalfEdge<T>::edge_type() const {
	if ( origin_ == nil ) return Invalid;
	if ( opposite_edge_ == nil ) return Invalid;
	if ( next_edge_ == nil ) return VirtualBorder;
	if ( face_ == nil ) return VirtualBorder;
	return Internal;
}

//! Find all faces that share this edge
/*!
 @return The faces that share this edge
 */
template <class T>
std::list< HalfEdgeFace<T>* > HalfEdge<T>::faces_around_edge() const {
	// Add this face, if edge does not belong to the virtual border
	std::list< HalfEdgeFace<T>* > res;
	if ( face_ != nil ) res.push_back(face_);

	// Try to add the opposite edge face
	if ( opposite_edge_ == nil ) return res;
	if ( opposite_edge_->face_ != nil ) res.push_back(opposite_edge_->face_);
	return res;
}

//=================================================================================
// Implementation of the HalfEdgeVertex class

//! Default constructor
template <class T>
HalfEdgeVertex<T>::HalfEdgeVertex() : leaving_edge_(nil), location_(nil) {}

//! Explicit constructor
/*!
 @param leaving_edge The edge pointing to this vertex
 @param pos The coordinates of this vertex
 */
template <class T>
HalfEdgeVertex<T>::HalfEdgeVertex(HalfEdge<T>* leaving_edge, const T& pos) : leaving_edge_(leaving_edge), location_(pos) {}

//! Copy constructor
/*!
 @param rhs The half-edge vertex to copy
 */
template <class T>
HalfEdgeVertex<T>::HalfEdgeVertex(const HalfEdgeVertex& rhs) : leaving_edge_(rhs.leaving_edge_), pos_(rhs.pos_) {}

//! Destructor
template <class T>
HalfEdgeVertex<T>::~HalfEdgeVertex() {}

//! Assignment operator
/*!
 @param rhs The half-edge vertex to copy
 */
template <class T>
HalfEdgeVertex<T>& HalfEdgeVertex<T>::operator=(const HalfEdgeVertex& rhs) {
	if ( &rhs != this ) {
		leaving_edge_ = rhs.leaving_edge_;
		pos_ = rhs.pos_;
	}
	return *this;
}

//! Accessor to the leaving edge associated to this vertex
/*!
 @return A pointer to the leaving edge associated to this vertex
 */
template <class T>
HalfEdge<T>* HalfEdgeVertex<T>::leaving_edge() const {
	return leaving_edge_;
}

//! Change the leaving edge associated to this vertex
/*!
 @param leaving_edge A pointer to the new leaving edge associated to this vertex
 @return True if function succeeded, false otherwise. Leaving edge may not be changed if client
         code provides a null pointer.
 */
template <class T>
bool HalfEdgeVertex<T>::set_leaving_edge(HalfEdge<T>* leaving_edge) {
	if ( leaving_edge == nil ) return false;
	leaving_edge_ = leaving_edge;
	return true;
}

//! Accessor to the location associated to this vertex
/*!
 @return A constant reference to the location associated to this vertex
 */
template <class T>
const T& HalfEdgeVertex<T>::location() const {
	return location_;
}

//! Change the location associated to this vertex
/*!
 @param location The new location associated to this vertex
 @return Always return true.
 */
template <class T>
bool HalfEdgeVertex<T>::set_location(const T& location) {
	location_ = location;
	return true;
}

//! Find all edges that share this vertex
/*!
 *  This function assumes that all edges around the vertex are connected
 *  together. If some of the edges are not connected, they will not be
 *  found by this function.
 *
 *  This function can be costly for border edges, since the get_previous_edge()
 *  function has to be called multiple times on such edges.
 *
 @return The edges that share this vertex
 */
template <class T>
std::list< HalfEdge<T>* > HalfEdgeVertex<T>::edges_around_vertex() const {
	std::list< HalfEdge<T>* > res;
	if ( leaving_edge_ == nil ) return res;

	// Iterate in forward direction
	bool border = false, first = true;
	for ( HalfEdge<T>* it = leaving_edge_; ( ( first == true ) || ( it != leaving_edge_ ) ); it = it->opposite_edge()->next_edge() ) {
		first = false;

		// A border edge was reached
		if ( it == nil ) {
			border = true;
			break;
		}

		// An internal edge was reached
		else {
			res.push_back(it);
		}
	}

	// If no border was reached, we are done with the sharing edges
	if ( border == false ) return res;

	// Iterate in backward direction
	for ( HalfEdge<T>* it = leaving_edge_->get_previous_edge(); it != nil; it = it->get_previous_edge() ) {
		res.push_front(it);
	}
	return res;
}

//! Find all faces that share this vertex
/*!
 *  This function assumes that all faces around the vertex are connected
 *  together. If some of the faces are not connected, they will not be
 *  found by this function.
 *
 *  This function can be costly for border edges, since the get_previous_edge()
 *  function has to be called multiple times on such edges.
 *
 @return The faces that share this vertex
 */
template <class T>
std::list< HalfEdgeFace<T>* > HalfEdgeVertex<T>::faces_around_vertex() const {
	std::list< HalfEdgeFace<T>* > res;
	if ( leaving_edge_ == nil ) return res;

	// Iterate in forward direction
	bool border = false, first = true;
	for ( HalfEdge<T>* it = leaving_edge_; ( ( first == true ) || ( it != leaving_edge_ ) ); it = it->opposite_edge()->next_edge() ) {
		first = false;

		// A border edge was reached
		if ( it == nil ) {
			border = true;
			break;
		}

		// An internal edge was reached
		else {
			if ( it->face() != nil ) res.push_back(it->face());
		}
	}

	// If no border was reached, we are done with the sharing edges
	if ( border == false ) return res;

	// Iterate in backward direction
	HalfEdge<T>* it = leaving_edge_;
	while ( it != nil ) {
		it = it->get_previous_edge();
		if ( it == nil ) return res;
		it = it->opposite_edge();
		if ( it == nil ) return res;
		if ( it->face() != nil ) res.push_front(it->face());
	}

	// Should never be reached
	return res;
}

//=================================================================================
// Implementation of the HalfEdgeFace class

//! Default constructor
template <class T>
HalfEdgeFace<T>::HalfEdgeFace() : edge_(nil) {}

//! Explicit constructor
/*!
 @param edge The edge pointing to this vertex
 */
template <class T>
HalfEdgeFace<T>::HalfEdgeFace(HalfEdge<T>* edge) : edge_(edge) {}

//! Copy constructor
/*!
 @param rhs The half-edge face to copy
 */
template <class T>
HalfEdgeFace<T>::HalfEdgeFace(const HalfEdgeFace& rhs) : edge_(rhs.edge_) {}

//! Destructor
template <class T>
HalfEdgeFace<T>::~HalfEdgeFace() {}

//! Assignment operator
/*!
 @param rhs The half-edge face to copy
 */
template <class T>
HalfEdgeFace<T>& HalfEdgeFace<T>::operator=(const HalfEdgeFace& rhs) {
	if ( &rhs != this ) {
		edge_ = rhs.edge_;
	}
	return *this;
}

//! Accessor to the edge associated to this face
/*!
 @return A pointer to the edge associated to this face
 */
template <class T>
HalfEdge<T>* HalfEdgeFace<T>::edge() const {
	return edge_;
}

//! Change the edge associated to this face
/*!
 @param edge A pointer to the new edge associated to this face
 @return True if function succeeded, false otherwise. Edge may not be changed if client
         code provides a null pointer.
 */
template <class T>
bool HalfEdgeFace<T>::set_edge(HalfEdge<T>* edge) {
	if ( edge == nil ) return false;
	edge_ = edge;
	return true;
}

//! Try to find the half-edge in this face whose opposite edge belongs to the other face
/*!
 *  This function assumes that all edges in this face are valid in the sense that they
 *  define a closed loop. There are several possible results if the face is invalid:<br>
 *  1. If face is a virtual exterior face, a null pointer will be returned.<br>
 *  2. If face defines an open half-edge path, a null pointer will be returned.<br>
 *  3. If face defines an invalid edge loop, this function will result in an infinite
 *     loop. An example of a face producing such an infinite loop could be: (example
 *     is written in pseudo-code)
 *  @code
 *  this_edge->next = edge1
 *  edge1->next = edge2
 *  edge2->next = edge3
 *  edge3->next = edge1
 *  @endcode
 *     Hence, the face defines a loop between edge1, edge2 and edge3, but
 *     never loops back to this_edge. Detecting such issues would be too
 *     costly to be practical - client code is therefore responsible for
 *     the validity of the face prior to calling this function.
 *
 @param rhs A constant reference to the other face
 @return The half-edge in this face whose opposite edge belongs to the other face. May be
         nil if no such half-edge can be found.
 */
template <class T>
HalfEdge<T>* HalfEdgeFace<T>::find_common_edge(const HalfEdgeFace& rhs) const {
	// Check face edge
	if ( edge_ == nil ) return nil;

	// Test the first edge
	HalfEdge<T>* res = edge_;
	HalfEdge<T>* opposite = res->opposite_edge();
	if ( opposite != nil ) {
		if ( opposite->face() == &rhs ) return res;
	}

	// Get to the next edge
	res = edge_->next_edge();
	if ( res == nil ) return nil;

	// Iterate through the half-edges until we loop back to the first edge
	while ( res != edge_ ) {
		// Test the opposite face
		opposite = res->opposite_edge();
		if ( opposite != nil ) {
			if ( opposite->face() == &rhs ) return res;
		}

		// Get to the next edge
		res = res->next_edge();
		if ( res == nil ) return nil;
	}

	// No such edge could be found
	return nil;
}

//! Try to find one half-edge vertex in this face which also belongs to the other face
/*!
 *  This function assumes that all edges in this face are valid in the sense that they
 *  define a closed loop. There are several possible results if the face is invalid:<br>
 *  1. If face is a virtual exterior face, a null pointer will be returned.<br>
 *  2. If face defines an open half-edge path, a null pointer will be returned.<br>
 *  3. If face defines an invalid edge loop, this function will result in an infinite
 *     loop. An example of a face producing such an infinite loop could be: (example
 *     is written in pseudo-code)
 *  @code
 *  this_edge->next = edge1
 *  edge1->next = edge2
 *  edge2->next = edge3
 *  edge3->next = edge1
 *  @endcode
 *     Hence, the face defines a loop between edge1, edge2 and edge3, but
 *     never loops back to this_edge. Detecting such issues would be too
 *     costly to be practical - client code is therefore responsible for
 *     the validity of the face prior to calling this function.
 *
 @param rhs A constant reference to the other face
 @return One half-edge vertex in this face which also belongs to the other
         face. May be nil if no such half-edge vertex can be found.
 */
template <class T>
HalfEdgeVertex<T>* HalfEdgeFace<T>::find_common_vertex(const HalfEdgeFace& rhs) const {
	// Check face edges
	if ( edge_ == nil ) return nil;
	if ( rhs.edge_ == nil ) return nil;

	// Try to find a common vertex between the faces
	// Iterate over the vertices of the first face
	bool first1 = true;
	for ( HalfEdge<T>* it = edge_; ( ( first1 == true ) || ( it != edge_ ) ); it = it->next_edge() ) {
		first1 = false;

		// Get the current vertex
		HalfEdgeVertex<T>* vertex = it->origin();

		// Iterate over the vertices of the second face to find a common one
		bool first2 = true;
		for ( HalfEdge<T>* it2 = rhs.edge(); ( ( first2 == true ) || ( it2 != rhs.edge() ) ); it2 = it2->next_edge() ) {
			first2 = false;
			if ( vertex == it2->origin() ) return vertex;
		}
	}

	// No such vertex could be found
	return nil;
}

//! Detect the type of the half-edge face
/*!
 *  This function solely tests the consistency of the half-edges that belong to this face. All
 *  face-adjacency informations are ignored, hence may be inconsistent even if this face is
 *  considered valid. To detect adjacency issues, please use the face_type() function.
 *
 *  This function is quite costly (especially for the detection of InvalidLoop faces) and should
 *  therefore be used sparingly, if possible for debugging purposes only.
 *
 @return The type of the half-edge. This can either be OpenPathFace for faces that are topologically
         opened, InvalidLoopFace for faces whose half-edges define an ill-defined closed loop, or
		 ValidFace for other faces.
 */
template <class T>
typename HalfEdgeFace<T>::FaceType HalfEdgeFace<T>::face_type() const {
	// Test the first edge
	if ( edge_ == nil ) return OpenPathFace;

	// Create a set of edges to remember which ones were already visited
	std::set< HalfEdge<T>* > edges;
	edges.insert(edge_);

	// Head to the next edge
	HalfEdge<T>* edge = edge_->next_edge();

	// Iterate through the half-edges
	while ( edge != edge_ ) {
		// Test current half-edge
		if ( edge == nil ) return OpenPathFace;
		if ( edges.find(edge) != edges.end() ) return InvalidLoopFace;

		// Add current half-edge to the visited half-edges and head to the next half-edge
		edges.insert(edge);
		edge = edge->next_edge();
	}

	// Face is valid
	return ValidFace;
}

//! Detect the adjacency type of the half-edge face
/*!
 *  This function assumes that edges in this face do not define an invalid edge loop,
 *  or this function would result in an infinite loop. An example of a face producing
 *  such an infinite loop could be: (example is written in pseudo-code)
 *  @code
 *  this_edge->next = edge1
 *  edge1->next = edge2
 *  edge2->next = edge3
 *  edge3->next = edge1
 *  @endcode
 *  Hence, the face defines a loop between edge1, edge2 and edge3, but never loops back
 *  to this_edge. Detecting such issues would be too costly to be practical - client
 *  code is therefore responsible for the validity of the face prior to calling this
 *  function.
 *
 @return The type of adjacency of the half-edge. This can either be OpenAdjacency for faces whose
         half-edges are not connected to another opposite half-edge, InconsistentOrientationAdjacency
		 if at least one of the adjacent face is not oriented consistently with this face,
		 UndefinedAdjacency if all half-edges cannot be traversed due to an internal invalidity
		 (please use the face_type() function to detect what, in the face, is inconsistent), or
		 ValidAdjacency for other faces.
 */
template <class T>
typename HalfEdgeFace<T>::AdjacencyType HalfEdgeFace<T>::adjacency_type() const {
	// Test the first edge
	if ( edge_ == nil ) return UndefinedAdjacency;
	if ( edge_->opposite_edge() == nil ) return OpenAdjacency;
	if ( edge_->opposite_edge()->origin() == edge_->origin() ) return InconsistentOrientationAdjacency;

	// Head to the next edge
	HalfEdge<T>* edge = edge_->next_edge();

	// Iterate through the half-edges
	while ( edge != edge_ ) {
		// Test current half-edge
		if ( edge == nil ) return UndefinedAdjacency;
		if ( edge->opposite_edge() == nil ) return OpenAdjacency;
		if ( edge->opposite_edge()->origin() == edge->origin() ) return InconsistentOrientationAdjacency;

		// Head to the next half-edge
		edge = edge->next_edge();
	}

	// Face is valid
	return ValidAdjacency;
}

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#endif
